\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{mathtext}
\usepackage[T1,T2A]{fontenc}
\usepackage[unicode]{hyperref} % to use russian in contents
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{mathbbol}
\textheight24.0cm
\textwidth17.0cm
\hoffset=-2.0cm \voffset=-1.0cm

\newcommand{\sz}{\scriptsize}
\newcommand{\noi}{\noindent}
\newcommand{\bc}{\begin{center}}
\newcommand{\ec}{\end{center}}

% THEOREMS -------------------------------------------------------
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Следствие}
\newtheorem{lem}[thm]{Лемма}
\newtheorem{theo}[thm]{Теорема}
\newtheorem{exampl}[thm]{Пример}
%\theoremstyle{definition}
\newtheorem{df}[thm]{Определение}
%\theoremstyle{remark}
\newtheorem{rem}[thm]{Замечание}
%\numberwithin{equation}{section}
% MATH -----------------------------------------------------------
\newcommand{\norm}[1]{\left\Vert#1\right\Vert}
\newcommand{\abs}[1]{\left\vert#1\right\vert}
%\newcommand{\set}[1]{\left\{#1\right\}}

\newcommand{\setn}[2]{\left\{#1_1, #1_2, ..., #1_#2\right\}}
\newcommand{\reln}[2]{\left\{#1_1, #1_2, ..., #1_#2\right\}}
\newcommand{\Real}{\mathbb R}
\newcommand{\Bool}{\mathbb B}

\newcommand{\bdd}{\mbox{BDD}}
\newcommand{\obdd}{\mbox{OBDD}}
\newcommand{\robdd}{\mbox{ROBDD}}
\newcommand{\srobdd}{\mbox{SROBDD}}
\newcommand{\dbdd}{\mbox{$\Delta$BDD}}

\begin{document}
\righthyphenmin=2
\sloppy
\thispagestyle{empty}
\bc
{\it Иванов Д.А., Терехов А.Н.}
\\
\Large {\bf Использование поиска-в-ширину в рекурсивно-переборных задачах}

\ec
\normalsize
%==================================================================0.
\vspace{200pt}
\section*{Аннотация}

\hspace*{0.6cm} В статье показано, что для переборных задач поиск-в-ширину с использованием специальной техники склеивания контекстов может дать выигрыш во времени относительно поиска-в-глубину. Авторами реализована библиотека для работы с диаграммами двоичных решений (\bdd{}), в листьях которых могут храниться скалярные значения. На нескольких экспериментах показана эффективность применения этой библиотеки к решению переборных задач. 

%===================================================================1.
\section*{Введение}

Ещё в конце пятидесятых годов XX-го века известный ленинградский учёный Г.С. Цейтин, работая на проблемой перевода естественных языков, предложил для учёта последующего контекста использовать специальные структуры данных, справедливо полагая, что аккуратная работа с этими деревьями может быть эффективней экспоненциальных возвратов. Однако этот метод очевидно требовал гораздо больше оперативной памяти, чем бэктреккинг, поэтому даже до экспериментов дело не дошло.

Через 20 лет А.Н. Терехов (в то время --- аспирант Г.С. Цейтина) всё-таки реализовал библиотеку для работы с условными значениями (деревьями специального вида) на ЭВМ ODRA 1204, придумал несколько существенных оптимизаций , которые ограничивали рост занимаемой памяти и применил эту технику в задаче синтеза эффективной объектной программы~\cite{Ter_sintez}. Тогда же по совету Д. Шварца (автора первого языка сверхвысокого уровня SETL) А.Н. Терехов предложил использовать свою технику для решения задач искусственного интеллекта методом поиска-в-ширину~\cite{Ter_candid}. Объём памяти ЭВМ того времени исчислялся только тысячами слов, а не гигабайтами, как сейчас, поэтому дело опять встало.

Ещё через 30 лет один из авторов этой статьи Д.А. Иванов, будучи аспирантом А.Н. Терехова, решил сделать третью попытку. Во-первых, объёмы памяти современных ЭВМ несоизмеримо больше, а, во-вторых, стала популярной идея применения техники \bdd{}, в рамках которой весьма эффективно решается задача поиска поддерева в дереве, являющаяся основой предлагаемого метода. \bdd{} появилась ещё в 1959 году~\cite{Lee}, но долгие годы использовалась только в научных экспериментах (по-видимому, по той же причине нехватки памяти ЭВМ). 
 
Поиск-в-глубину и поиск-в-ширину --- это хорошо известные алгоритмы из теории графов, позволяющие обходить вершины графа и отличающиеся порядком перебора вершин. Для поиска-в-ширину хорошо изучен классический подход, когда множество вершин представляется в виде очереди, а граф задан явно и хранится в памяти, например, в виде списка вершин с ребрами или матрицы смежности. В данной статье будут рассматриваться неявно заданные деревья и графы, образованные рекурсивной процедурой. Рекурсия --- это стандартный способ решения переборных задач: всё множество перебираемых решений находится на последнем уровне рекурсии (листьях графа). Узлами графа являются процедуры, а рёбрами --- рекурсивные вызовы внутри тела процедуры. В листьях происходит проверка, является ли построенное решение на самом деле решением.

Во многих задачах поиска в каком-то смысле оптимального решения варианты, возникающие в процессе поиска решения, не зависят друг от друга или зависят не слишком сильно. Например, при генерации объектного кода~\cite{Ter_register}, занятие регистра для какого-то промежуточного результата никак не влияет на следующие действия, пока регистров хватает. Во многих задачах многокритериальной оптимизации принятие решения по выбору одного параметра мало влияет на выбор значений других параметров. Эти соображения подтолкнули нас к исследованию алгоритмов поиска-в-ширину, в которых уже принятые решения хранятся в специальных структурах данных, позволяющих в большинстве случаев не пересчитывать их заново, что позволит существенно (в разы) выиграть по времени при таком проигрыше в памяти, который позволителен в современных ЭВМ.

В качестве модельных примеров мы рассмотрим задачу о назначениях, задачу расстановки 8-ми ферзей и решение шахматных этюдов. Кто-то может возразить, что шахматные задачи хорошо изучены, для них найдено множество эффективных алгоритмов, а для задачи от назначениях (частного случая задачи о расписании) существует полиномиальный алгоритм, находящий максимальное паросочетание в двудольном графе. Но нас и не интересуют эти задачи как таковые. Мы проводим эксперимент: есть переборная задача, в абсолютно одинаковых условиях, с использованием одной и той же библиотеки мы сравниваем два способа перебора и определяем, какой способ выигрывает во времени счёта. Кроме того, на наш выбор модельных задач повлиял тот факт, что классик Карл Хьюит --- создатель, по-видимому, первого языка искусственного интеллекта PLANNER~\cite{Hew} также начинал с задачи о 8-ми ферзях. Поиск-в-ширину в нашей реализации выигрывает, когда удаётся переиспользовать контексты, причём чем больше, тем лучше. 

Сам по себе алгоритм поиска-в-ширину известен и широко представлен в публикациях (см., например,\cite{Bur},\cite{Gar}), однако мы считаем, что предложенный нами метод является более общим решением, примерно, как бэктреккинг для поиска-в-глубину. Как часто бывает в программной инженерии (в отличие от информатики --- Computer Science), появление эффективного алгоритма, нового решения, пусть даже не самого общего, но покрывающего достаточно широкий класс задач, в корне меняет оценку применимости тех или иных методов. Идея, придуманная Г.С.Цейтиным более 60 лет назад, не могла быть реализована на ЭВМ тех лет, 20 лет спустя А.Н.Терехов провел первые машинные эксперименты, а реализация Д.А.Ивановым библиотеки \bdd{} на языке OCaml послужила «спусковым крючком» для полноценной реализации идеи в наши дни. Впечатляющие результаты, полученные при решении задач шахматных этюдов (в качестве первого примера) дают основание авторам полагать, что развитие этой идеи может принести пользу во многих задачах.

%%==================================================================1.
\section{Формализация методов}

\subsection{Дерево решений}

Многие переборные задачи по своей природе имеют рекурсивную структуру. Например, в задаче о восьми ферзях, мы для каждого расставленного на вертикали $k$  ферзя пытаемся поставить ферзя на $(k+1)$-ю вертикаль и смотрим, не бьет ли его один из уже расставленных ферзей.
Если нет --- то повторяем рекурсивно. Таким образом, отрезается целый пласт возможных решений, причём чем меньше вертикаль, тем больше размер отрезаемого подмножества.

При рекурсивном алгоритме решения мы как бы обходим некоторое виртуальное дерево, где узлами высоты $k$ служат вызовы процедуры на уровне (вертикали) $k$, а листьями --- возможные решения.

Общий вид решения рекурсивно-переборной задачи:

\begin{verbatim}
Set<E> solveAllDeepFirst() {
    void inner(int level, E acc) {
        if (level == LEAF_LEVEL) {
            if (f(acc)) res.add(acc);
        } else {
            for (int i=0; i<NBRANCHES; i++) {
                E newacc = acc.acumulate(i);                 //Пытаемся добавить
                if (newacc != null) inner(level+1, newacc);
            }
        }
    }

    Set<E> res = new Set<E>();
    inner(0, new E());
}
\end{verbatim}

 \begin{rem} Мы записали алгоритм решения абстрактной задачи, когда требуется найти все решения. Если нам нужно единственное решение, алгоритм можно модифицировать очевидным образом.
 \end{rem}

\begin{rem} Мы прибегли к некоторым упрощениям сознательно. Количество уровней и количество веток на данном уровне могут быть не константами, а вычисляться динамически. На общую суть это не влияет.
\end{rem}

Аккумулируемое решение E должно поддерживать операцию \verb|accumulate(i)|, которая перестраивает промежуточное решение на основе того, по какой ветке дерева решений мы собираемся пойти, и выдаёт \verb|null| в случае, когда данная ветка заведомо не даст ни одного решения (отсечение).

\subsection{Поиск-в-ширину}

Очевидно, что при рекурсивном подходе дерево обходится в глубину. Мы считаем, что при правильном выборе структур данных и грамотной организации хранения информации, скорость работы можно увеличить в разы, если использовать метод поиска-в-ширину. В данной статье подобной структурой данных выступает диаграмма двоичных решений, усовершенствованная для хранения различных типов данных.

Запишем алгоритм решения задачи о назначениях методом поиска-в-ширину. Если подходить к алгоритму классически, то мы должны хранить список построенных к данному моменту возможных расстановок и увеличивать его на количество ресурсов при переходе к следующей итерации:

\begin{verbatim}
List<int[]> assignBreadFirst(Timetable t) {
    List<int[]> lst = new List<int[]>();
    lst.add(new int[]);
    for (int i=0; i<t.getSize(); i++) {
        List<int[]> newlst = new List<int[]>();
        while (lst.hasNext()) {
            int[] x = lst.next();
            for (int j=0; j<t.getConsumerResources(i); j++) {

                //Пытаемся добавить в решение на позицию i ресурс j
                //Если ресурс был занят ранее, accumulate выдаёт null
                int[] newX = accumulate(x, i, j);
                if (newpos != null) newlst.add(newpos);
            }
        }
        lst = newlst;
    }
    return lst;
}
\end{verbatim}


Разумеется, в таком виде решение крайне неэффективно. Мы по сути храним контекст всех возможных процедур-узлов на данном уровне дерева решений в виде списка. Размер списка растёт экспоненциально, и мы быстро выбьемся за разумные рамки памяти, не получив выигрыша по времени.

Как улучшить такой поиск-в-ширину? Ответ --- использовать для хранения контекстов не список, а структуру данных, позволяющую оптимизировать память и время за счёт исключения хранения повторяющихся частей контекста. Кроме того, дерево решений можно превратить в DAG (Directed Acyclic Graph) --- вместо хранения повторяющейся части мы можем поставить на неё ссылку. При поиске-в-глубину (рекурсии) это называется динамическим программированием, или мемоизацией (memoization), и обычно проводится, когда накопленная часть контекста позволяет кэширование. Чаще всего такая техника применяется, когда контекст --- это целое число. Тогда для хранения решений можно использовать обычный массив.  При входе в рекурсивную процедуру с параметром \verb|e|, мы сначала проверяем, не содержит ли массив уже построенных решений \verb|e|, а затем уже выполняем тело процедуры, попутно пополняя массив.

Эта техника не работает, когда контекст сложный, так как массив может оказаться очень большим. Опять же, нужна специальная структура данных. Сформулируем общие требования к такой структуре на основе алгоритма, приведённого выше.

Структура должна:
\begin{itemize}
\item Хранить произвольные типы данных
\item Позволять строить такую же структуру на следующей итерации, изменяя хранящиеся в ней контексты.
\item Легко конвертироваться в \verb|Set|, \verb|List| или итерироваться (чтобы выдавать результат).
\end{itemize}


Попробуем записать общий вид алгоритма поиска-в-ширину в переборно-рекурсивной задаче.

\begin{verbatim}
Set<E> solveAllBreadFirst() {
    ContextStorage<E> ctx = new ContextStorage<E>();
    ctx = ctx.add(new E());
    for (int i=0; i<LEAF_LEVEL; i++) {
        //Разветвляем каждый хранящийся контекст на NBRANCHES ветвей.
        ctx = ctx.accumulate(NBRACHES);
    }

    return ctx.toSet();
}
\end{verbatim}

Разумеется, все сложность и хитрость заключаются в операции \verb|accumulate(NBRANCHES)| и внутреннем устройстве контекста. Кроме того, надо определить операцию \verb|toSet()|, чтобы выдать результат работы алгоритма в приемлемой форме.

%%==================================================================1.
\section{Диаграмма двоичных решений}

\subsection{Математические основы \bdd{}}
В этом разделе мы опишем \bdd{} с математической точки зрения, познакомимся с различными видами \bdd{}, а также увидим, как
производить операции над ними и выражать множества и отношения через логические формулы.
Основные идеи и определения взяты из~\cite{Bry} и~\cite{And}.

\subsubsection{\bdd{}, сокращенные \bdd{} и разделяемые сокращенные \bdd{}}
Чтобы дать определение \bdd{}, нам потребуются две нестандартные конструкции матлогики:
\begin{df}
\emph{if-then-else оператором} называется синтаксическое расширение логических выражений. Новое выражение записывается
$e \rightarrow e_1,e_2$ и семантически эквивалентно $(e \Rightarrow e_1) \land (\neg e \Rightarrow e_2)$.
\end{df}

\begin{df}
\emph{if-then-else нормальной формой} булевской функции (сокращённо, \emph{INF}) называется форма записи
логического выражения, которая соответствует грамматике:
\begin{tabular}{r l}
  $E\ ::=$    &     $\ C\ |\ V \rightarrow E,E$. \\
\end{tabular}
\end{df}
\begin{exampl}
Выражение $x \land y \land \neg z$ в INF будет выглядеть как \mbox{$x \rightarrow (y \rightarrow (z \rightarrow 0, 1), 0), 0 $}.
\end{exampl}


\begin{theo} \emph{Закон раскрытия Шэннона} (Shannon expansion's Law).\\
\begin{displaymath}
e\quad \equiv\quad x \rightarrow e[1/x],e[0/x]
\end{displaymath}
где $e[a/x]$ --- это логическое выражение, в котором в переменную $x$ подставлено значение $a$

\end{theo}
\begin{cor}
Любое логическое выражение можно записать в INF.
\end{cor}

Итак, теперь мы готовы определить диаграммы двоичных решений. \bdd{} есть ни что иное, как INF логического
выражения, представленная в виде графа.
\begin{df}
\emph{Binary Decision Diagram} --- это направленный, ацикличный, корневой граф $t = (V,E)$ такой, что:
\begin{itemize}
\item все дуги делятся на два равных множества $One$ и $Zero$;

\item есть две специальных вершины: \mbox{\emph{0-терминал}} и \mbox{\emph{1-терминал}},
представляющие тождественные истину и ложь. Они называюся терминальными.
Это единственные вершины, которые не имеют выходящих рёбер,
т.е. $\forall (v_1,v_2) \in E\quad v_1 \neq 1\textrm{-терминал} \land v_1 \neq 0\textrm{-терминал}$;

\item \mbox{$\forall v \in V \setminus \{0,1\}\quad \exists ! (v_1,v_2) \in One : v_1=v\ \land\ \exists ! (v_1',v_2') \in Zero : v_1'=v$},
т.е. любая вершина, кроме терминальной, имеет ровно две исходящие дуги: одна из множества $One$, а другая из $Zero$.
Потомки данной вершины называются $one(x)$ и $zero(x)$ соответственно;

\item Все вершины, кроме терминальных, помечены элементом из множества $ X = \{x_1,...,x_n\}$ (множество переменных).
Эта метка называется \textbf{переменной} вершины $v$ и обозначается $var(v)$.
\end{itemize}
\end{df}

\begin{rem}
    Для логических выражений \bdd{} более компактно описывает таблицу истинности, определённую для переменных $x_1,...,x_n$.
\end{rem}

\begin{rem}
Будем обозначать $root(t)$ корневую вершину \bdd{} $t$.
\end{rem}

Мы получили довольно широкий класс графов. Для эффективного хранения и манипуляций с данными надо наложить на
\bdd{} некоторые ограничения, т.е. сузить этот класс. Будем считать, что на множестве $X$ задан линейный порядок ``<''.
\begin{df}
\emph{Упорядоченной диаграммой двоичных решений} (Ordered Binary Decision Diagram, \obdd{}) называется такая \bdd{}, что
на любом пути $(v_1,...,v_k)$, помеченном переменными $(x_{v_1},...,x_{v_k})$, соблюдается линейный порядок ``<'', т.е.
$\forall i,j : i<j \quad (x_{v_i} < x_{v_j})$.
\end{df}

\begin{df}
\emph{Разделяемой сокращенной упорядоченной диаграммой двоичных решений} (Shared Reduced Ordered Binary Decision Diagram, SROBDD)
называется такая \obdd{}, что для любых нетерминальных вершин $v_1,v_2 \in V \setminus \{0,1\}:$
\begin{itemize}
\item $one(v_1) \neq zero(v_1)$;
\item Если \mbox{$(one(v_1)=one(v_2)\land zero(v_1)=zero(v_2)\land var(v_1)=var(v_2))$}, то $v_1\ =\ v_2$.
\end{itemize}
Кроме того, все \bdd{} разделяют между собой вершины.
\end{df}
\begin{rem}
Вышеозначенные условия называются \emph{свойствами минимальности} \robdd.
\end{rem}
\begin{rem}
Слово \emph{``разделяемая''} обычно опускают. Таким образом, \srobdd превращается в \robdd{}.
\end{rem}
\begin{rem}
Чаще всего, когда говорят \bdd{}, имеют в виду именно \robdd{}. Кроме того, в алгоритмах отождествляют \bdd{} и её корневую вершину.
\end{rem}
\begin{rem}
Преимущество \robdd{} по памяти заключается в исключении хранения повторяющихся частей. Все операции над \robdd{} можно реализовать с широким использованием хэш-функций.
\end{rem}

Логическая формула, соответствующая \bdd{} с корневой вершиной $v$, записывается $e^{v}$ и
определяется рекурсивно следующим образом:
\begin{itemize}
\item если $v=0$, то $e^{v} = 0$;
\item если $v=1$, то $e^{v} = 1$;
\item иначе $e^{v} = var(v) \rightarrow e^{one(v)},e^{zero(v)}$.
\end{itemize}

\begin{exampl}
На рисунке ~\ref{ex_bdd} изображены
два логических выражения, представленные в виде \bdd{}, \obdd{} и \robdd{} соответственно:
\mbox{$e_1\ =\ (x_1 \land x_2 \land x_3) \lor (\neg x_1 \land \neg x_3 \land\ \neg x_2)  $} и
\mbox{$e_2\ =\ \ (x_1 \Rightarrow (x_3 \land x_2)) \land (\neg x_1 \Rightarrow (x_2 \lor \neg x_2))$}\\


\end{exampl}

\begin{rem}
При изображении \bdd{} приняты несколько правил:
\begin{itemize}
\item Все вершины, кроме терминальных, изображаются кругами, а терминальные --- квадратами;
\item Внутри вершины пишется номер переменной, которой помечена эта вершина;
\item Дуги из множества $One$ рисуются сплошными линиями, а из множества $Zero$--- штрихованными.
\end{itemize}
В изображениях \bdd{} для предыдущего примера корневые вершины были помечены дополнительно метками $e1$ и $e2$,
чтобы понять, какая вершина какому \bdd{} соответствует.
\end{rem}

\begin{lem} \emph{Единственности}~\cite{Bry}. \\
Для любой булевской функции \mbox{$f:\mathbf{B}^n \rightarrow \mathbf{B}$}
при заданном линейном порядке переменных ``<'', таком
что $x_1<x_2<...<x_n$, существует единственная \robdd{} с корневой вершиной $v$, такая что для любой интерпретации
\mbox{$I \quad e^{v}[I(x_1)/x_1,...,I(x_n)/x_n]=f(I(x_1),...,I(x_n))$}.
\end{lem}


\bdd{}, соответствующую логическому выражению $e$, будем записывать  как $bdd(e)$, а \bdd{}, соответствующую
булевской функции $f$, как $bdd(f)$.

Можно отметить, что проверка общезначимости, выполнимости и эквивалентности осуществляется
за одну операцию сравнения:
\begin{itemize}
\item $e$ общезначимо $\Leftrightarrow$ $root(bdd(e))$ --- $1$-терминал;
\item $e$ выполнимо $\Leftrightarrow$ $root(bdd(e))$ --- любая вершина, кроме $0$-терминала;
\item $e_1 \equiv e_2 \quad \Leftrightarrow \quad root(bdd(e_1))=root(bdd(e_2))$.
\end{itemize}

Заметим, что если выражение находится в КНФ, то проверка общезначимости --- NP-полная задача. Проверка
выполнимости для ДНФ тоже сложная задача (co-NP). В \robdd{} проверка действительно осуществляется за одну операцию
сравнения, однако построение выражения
в худшем случаем может занять экспоненту по времени от количества переменных.


Заметим, что размер \robdd{} может сильно варьироваться в зависимости от порядка переменных
(см. рис.~\ref{varorder}). Таким образом возникает
ещё одна задача --- поиск оптимального порядка переменных. Однако, как показывает практика, при решении определённых задач
лучше изначально задать некий порядок переменных, а не перестраивать его на ходу, используя эвристики, как делает,
например, BuDDy~\cite{buddy}.

Обычно вершина \robdd{} содержит переменную, как целое число. Линейный порядок на переменных в этом случае задаётся отношением
``<'' на целых числах.

\subsubsection{Операции над \bdd{}}
В этом подразделе будет показано, как можно строить \bdd{} из логических выражений и эффективно производить операции различного рода:
бинарные, кванторные, решать задачу выполнимости (Satisfability, SAT). Представленные алгоритмы --- это операции над \robdd{}.

Для начала, мы полагаем, что все вершины лежат в массиве или в таблице $T$, ключ которой --- это целое число.
Будем считать, что вершины занумерованы натуральными числами. Тогда в качестве значения $T(v)$ хранит тройку
$(var(v),one(v),zero(v))$. Этого вполне достаточно для представления графа, однако для эффективной работы нам потребуется обратная таблица $H : (var,one,zero) \mapsto v$.

Мы добавляем очередную вершину только в случае, если она раньше не встречалась. Это проверяется по таблице $H$. Следующий алгоритм отвечает за добавление вершины и проверяет выполнение свойства минимальности \robdd{}.

\begin{verbatim}
Insert (var, low, high) : Node =
  if low = high then
    return low
  else
    u := H(var, low, high)
    if u <> null then
       return u
    else
      v := generate_next_node()
      add (v -> (var, low, high)) into T
      add ((var, low, high) -> v) into H
      return v
    endif
  endif
\end{verbatim}

В худшем случае, количество вершин может возрасти экспоненциально от числа переменных. Однако обычно, на практических примерах, выбирая правильный порядок переменных, удаётся избежать экспоненциального взрыва за счёт кэширования.

Следующий шаг заключается в эффективной реализации бинарных операций. Классическим считается следующий алгоритм:
\begin{verbatim}

/*вспомогательная функция; сужение e(v) на vr=1*/
opt_one(v, x) : Node =
  if var(v) = x then one(v)
  else v

/*вспомогательная функция; сужение e(v) на vr=0*/
opt_zero(v, x) : Node =
  if var(v) = x then zero(v)
  else v

/*основная рекурсивная процедура/
Apply(v1, v2, op):Node =
  v := D(v1, v2, op);
  if v <> null then return v
  else
    if isTerminal(v1) && isTerminal(v2) then v := op(v1, v2)
    else
      x := min(var(v1), var(v2))
      v := insert(x,
             Apply(opt_one(v1,x),  opt_one(v2,x),  op),
             Apply(opt_zero(v1,x), opt_zero(v2,x), op))
      add ((v1,v2,op) -> v) into D
      return v
  endif

\end{verbatim}

Здесь таблица D выступает в роли кэша операций. Если реализовывать алгоритм без нее, то произойдет экспоненциальный взрыв,
как нетрудно заметить. Чтобы этого избежать, применяется динамическое программирование.
Алгоритм принимает на вход две \bdd{} и бинарную операцию,
после чего рекурсивно ``спускается'' до терминалов.
Работа алгоритма основана на следствии закона раскрытия Шэннона :
\begin{displaymath}
t_1\ \underline{op}\ t_2\ \equiv\ x \rightarrow (t_1[1/x]\ \underline{op}\ t_2[1/x]),(t_1[1/x]\ \underline{op}\ t_2[0/x])
\end{displaymath}

Важными операциями являются сужение $e[b/x]$, кванторы и суперпозиция. В \cite{Bry} считается, что, хотя в худшем случае бинарные операции работают за $O(nm)$ (где $n$ и $m$ --- количество вершин в \robdd{}), в среднем это время составляет $O(n+m)$.

Существуют также алгоритмы для определения интерпретаций, на которых значение логического выражения,
соответствующее \bdd{}, истинно.

Вот три стандартные операции:
\begin{itemize}
\item \emph{SatAny(v)} --- выдаёт произвольную интерпретацию, которая выполняет $e^v$;
\item \emph{SatAll(v)} --- выдаёт все интерпретации, которые выполняют $e^v$;
\item \emph{SatCount(v)} --- выдаёт число выполняющих интерпретаций.
\end{itemize}
Все алгоритмы завязаны на рекурсивный обход дерева. Подробнее об алгоритмах для этих операций можно узнать,
например, в~\cite{And}.

\subsubsection{\bdd{} с произвольными значениями на листьях}
Разумеется, вместо просто одних только логических значений на листьях, мы можем использовать любой тип данных, например, целые числа или строки. В этом случае, набор операций над \bdd{} расширяется на все операции, соответствующие данному типу данных, так как \bdd{} есть не что иное, как функция с областью значений в данном типе. Для целочисленных \bdd{} мы можем определить сложение, умножение, if-then-else и т.д. Такие обобщённые \bdd{} делались и ранее~\cite{Cla},\cite{Sas}.

Хотя нам подходит абсолютно произвольный тип данных, для эффективности по памяти за счёт "схлопывания веток" (при нахождении повторяющегося поддерева мы вместо копирования ставим на него ссылку) лучше, чтобы количество различных листьев было бы минимальным. Это надо учесть при составлении алгоритма. Например, если мы должны оперировать с массивом значений, лучше разбить \bdd{} на \bdd{} для отдельных ячеек.

Теперь у нас есть все необходимые операции для нашего хранилища контекстов. Можно использовать \bdd{} с произвольными значениями на листьях для реализации поиска-в-ширину на переборных задачах и сравнения полученных результатов с классическим рекурсивным подходом.

%%==================================================================1.
\section{Использование \bdd{} для поиска-в-ширину}

%%==================================================================1.
\subsection{Задача о расписании}
Мы готовы написать класс ContextStorage для алгоритма поиска-в-ширину. Запишем костяк:

\begin{verbatim}
 int index = 0;
 public ContextStorage(Timetable t) {
    consumer = new Bdd[t.getSize()];
   for (int i=0; i<consumer.length; i++) {
      //Для каждого потребителя создаём BDD, на листьях которого находятся номера
      //всех ресурсов, ему соответствующих, и спец. ресурс '-1' (null)
      //Важно, что переменные у каждого BDD-дерева уникальны
	  consumer[i] = Bdd.makeConst(-1).insertNewList(t.getConsumerResources(i));
   }
 }

 public void accumulate() { //NBRANCHES нам не нужен
   for (int i=0; i<index; i++) {
     //'Пересекаем' с деревьями всех предыдущих потребителей
     // Операцию condNE следует читать как 'a := if (a!=b) then a else -1'
     consumer[index] = consumer[index].condNE(consumer[i], -1);
   }
   index++;
 }
\end{verbatim}
На каждой итерации мы вызываем метод \verb|accumulate| (см. Общий алгоритм поиска-в-ширину). \bdd{}-дерево, соответствующее последнему потребителю, даст нам полное представление о всех решениях.
Итак, сравниваем работу для достаточно плохого случая (все ветки поиска-в-глубину обходятся). Матрица ресурсов выглядит следующим образом (строка --- это список ресурсов
доступных данному потребителю):

\begin{verbatim}
0 1 2 3 4
1 2 3 4
2 3 4
3 4
4
\end{verbatim}

Сравнение двух методов по времени исполнения в зависимости от количества ресурсов можно увидеть на таблице~\ref{table1}.

Прослеживается тенденция: время рекурсивного алгоритма возрастает в 5 раз с добавлением нового ресурса, а время поиска-в-ширину только в 2. Задача о расписании содержит много повторяющихся частей контекста, и за счёт этого механизм \bdd{} экономит время, не пересчитывая одно и тоже много раз.


\subsection{Задача о восьми ферзях}

Попробуем определить класс ContextStorage из обобщённого алгоритма для поиска-в-ширину, данного ранее, для ещё одной классической переборной задачи --- задачи о восьми ферзях. Во-первых, класс должен быть построен с использованием \bdd{}. Во-вторых, содержать в качестве листьев позицию ферзей на вертикали, а не всю текущую позицию на доске (чтобы дать возможность различным веткам "схлопнуться").

\begin{verbatim}
class ContextStorage<Position> {
    BDD<int>[] verts;
    int current;

    public ContextStorage(int nverts) {
        verts = new BDD<int>[nverts];
        current = 0;
    }
    public void add(int nbraches) {
        verts[current] = makeSet(nbranches);
        for (int i=0; i<current; i++) {
            // Обнуляем ветку, если выполнено условие
            verts[current] = verts[current].condNull(BDD.disj (

                // На текущей горизонтали
                verts[i].equals(verts[current]),

                // На диагонали
                verts[i].sub(verts[current]).abs().equals(new BDD(current-i)))
            );
        }
    }

    public void Set<Position> toSet() {
        //Выдаются позиции на основе BDD.iter()
    }
}
\end{verbatim}

Теперь надо запустить два алгоритма и провести сравнительный анализ. Все замеры производились для программ на языках \emph{Java} и \emph{OCaml}, c помощью реализованных полностью на этих языках собственных библиотек~\cite{ocamlbdd}. Стандартные реализации \bdd{} вроде \cite{buddy} и \cite{cudd} не использовались, хотя они могут дать определённый выигрыш за счёт того, что реализованы на языке "Си".

При сравнении с классическим алгоритмом, новый метод проигрывает в производительности. Ничего удивительного в этом нет. Ситуация возникает из-за того, что задача о восьми ферзях --- это \textbf{полный} перебор решений. Мы не можем наблюдать преимуществ использования \bdd{}, так как количество веток растёт экспоненциально, и они не "схлопываются". Все решения сильно отличаются, контексты разные, нет совпадающих частей. Это пример неудачного использования поиска-в-ширину.


\subsection{Задача шахматного этюда}
Напоследок, сравним два метода в решении более сложной переборной задачи. На шахматной доске расставлена позиция. Требуется поставить мат оппоненту за заданное количество шагов.

Количество ветвей на каждый полуход приблизительно равно (количество фигур) * (возможных ходов у фигуры в среднем). Например, для позиции, где у обоих сторон есть ферзь, ладья, слон и король, количество возможных вариантов (за вычетом малого) в свой ход равно $7*4 + 7*2 + 7*2 + 8 = 64$. Если мы должны поставить мат в 3 хода (5 полуходов), то это около 800 миллионов вариантов, каждый из которых --- не атомарное действие, а вызов сложного метода.

В чём выигрыш \bdd{}? Состоянием системы при входе в метод можно назвать позицию на доске и количество ходов, оставшихся до мата. Очевидно, хранить состояния для динамического программирования в поиске-в-глубину мы не можем, так как их очень много.
Поиск-в-ширину помогает слить многие варианты в один. Самая важная мысль --- сделать отдельные \bdd{} для каждой фигуры и с каждым полуходом наращивать.  Очевидно, что если игрок подвинул слона, то состояние ферзя не изменится, а после хода противника состояние фигуры может измениться, только если её взяли. В свой полуход \bdd{} фигуры по высоте увеличивается на логарифм от количества ходов этой фигуры, а в чужой зависит от количества вариантов, при которой её берут (оно не велико).

Проведём сравнительный анализ двух методов. Для мата в один ход побеждает поиск-в-глубину, но когда мы увеличиваем количество ходов, множитель для поиска-в-ширину значительно ниже, чем для поиска-в-ширину. Для приведённого выше примера на каждый новый ход добавляется примерно $4000$ вариантов. Соответственно, время работы можно умножать на 4000, но для \bdd{} такой показатель: 300 -- 2000. Увеличение числа фигур также сказывается на скорости. Причём, чем больше фигур, тем эффективнее поиск-в-ширину относительно поиска-в-глубину по изложенным выше причинам.


\section{Заключение}

Поиск-в-ширину --- мощный инструмент решения переборных задач, требующий, однако, вспомогательных структур данных, сложно устроенных внутри. На современных компьютерах при большом объёме памяти \bdd{} позволяют эффективно решать сложные проблемы, предполагающие общность промежуточных данных. По сути, мы выносим хранение контекста из стека рекурсивной функции в диаграмму двоичных решений, а она, в свою очередь, "схлопывает" ветки вызовов.

Программирование в стиле поиска-в-ширину требует определённых навыков и библиотеки поддержки. Важными становятся детали, например, порядок переменных в \bdd{}. В настоящей статье описан общий подход и показаны известные примеры переборных задач, решаемых новым способом. \bdd{} применяется для решения задач системного программирования, например, анализа указателей \cite{Wha}. Кроме того, для дальнейшего исследования остаётся использование ZBDD~\cite{zbdd} и других типов \bdd{}.

%============================================================

\newpage

\section{Список литературы}
\begin{thebibliography}{99}

\bibitem{Ter_sintez} Терехов А.Н., Цейтин Г.С. Средства эффективного синтеза объектной программы, Программирование, N6, 1975.

\bibitem{Ter_candid} Терехов А.Н. Методы синтеза эффективной рабочей программы, \mbox{$http://ant.tepkom.ru/newsite/publications/doc/Terekhov\_PhD\_thesis.pdf$}.
    
\bibitem{Lee} C.Y. Lee. Representation of Switching Circuits by Binary-Decision Programs. Bell Systems Technical Journal, 38:985-999, 1959.

\bibitem{Ter_register} Терехов А.Н. Распределение регистров в рабочей программе, Программирование, N1, 1977.

\bibitem{Hew} Hewitt C. Description and theoretical analysis (using schemata) of Planner: A language for proving theorems and manipulating models in a robot AI Memo No. 251, MIT Project MAC, April 1972.

\bibitem{Bur} И. Б. Бурдонов. Обход неизвестного ориентированного графа конечным роботом. Программирование, N4, 2004.

\bibitem{Gar} A. Gurfinkel. A Survey of Graph-based Algorithms in Software Model Checking, CAV 2001.

\bibitem{Bry} Randell E. Bryant. Symbolic Boolean manipulations with ordered binary decision diagrams.
ACM Computer Surveys, 24(3):293-318, September 1992.

\bibitem{And} Henric Reif Andersen. An introduction to Binary Decision Diagrams. Lecture notes for 49285
Advanced Algorithms E97, October 1997.

\bibitem{buddy} Jorn Lind-Nielsen. BuDDy: Binary Decision Diagram package. IT-University of Copenhagen (ITU),
November 9, 2002.

\bibitem{cudd} Fabio Somenzi. CUDD: CU Decision Diagram Package. Departament of Electriacal and Computer Engineering.
University of Colorado at Boudler. May 17, 2005.

\bibitem{Cla} E. Clarke, M. Fujita, X. Zhao. Applications of Multi-Terminal Binary Decision Diagrams. CMU-CS-95-160, 1995

\bibitem{Sas} T. Sasao, S. Nagayama. Representation of Elementary Functions Using Binary Moment Diagrams. 36-th International Symposium of Multiple-Valued Logic (ISMVL'06), 2006.

\bibitem{ocamlbdd} OCamlBdd library, http://oops.math.spbu.ru/projects/ocamlbdd/

\bibitem{Wha}J. Whaley and M. Lam. Cloning-based context-sensitive pointer alias analyses using binary decision diargrams. In: Prog. Lang. Design and Impl. , 2004.
    
\bibitem{zbdd} Shin-ichi Minato. Zero-suppressed BDDs for set manipulation in combinatorial problems, DAC~'93: Proceedings of the 30th international conference on Design automation, 1993.

\end{thebibliography}

\newpage
\section*{Авторы}
\begin{itemize}
\item
\emph{Иванов Дмитрий Аркадьевич}, соавтор статьи. С отличием закончил математико-механический факультет СПбГУ. В настоящий момент пишет диссертацию на тему "Использование эффективных структур данных в задачах анализа программ". Работает в компании JetBrains.
\\
Контакты: +7(906)227-18-37, korifey@gmail.com


\item
\emph{Терехов Андрей Николаевич}, соавтор статьи, научный руководитель. С отличием закончил математико-механический факультет Ленинградского Государственного Университета. Доктор физико-математических наук, профессор, заведующий кафедрой системного программирования СПбГУ. Председатель Правления ассоциации разработчиков программного обеспечения РУССОФТ, генеральный директор ИТ-компании \emph{Ланит-Терком}.
\\
Контакты: +7(911)922-69-86, Andrey.Terekhov@lanit-tercom.com
\end{itemize}

\newpage
\section*{Рисунки и таблицы}
\begin{table}[h]
\centering
\begin{tabular}{|c|c|c|}
\hline
 $N$ ресурсов & Поиск-в-глубину (ms)  &  Поиск-в-ширину (ms) \\
\hline
 11 & 141 & 187 \\
\hline
 12 & 687 & 374 \\
\hline
 13 & 3682 & 594 \\
\hline
 14 & 21138 & 1171 \\
\hline
\end{tabular}
\caption{Сравнение алгоритмов для задачи о назначениях}
\label{table1}
\end{table}

\begin{figure}[h]
  \centering
  \includegraphics[height=0.18\textheight ]{./pic/ex-bdd.ps} \\
  \includegraphics[height=0.18\textheight ]{./pic/ex-obdd.ps} \\
  \includegraphics[height=0.18\textheight ]{./pic/ex-robdd.eps}
  \caption{Представление выражений в виде BDD, OBDD и ROBDD}\label{ex_bdd}
\end{figure}

\begin{figure}[htb]
  \centering
  \includegraphics[width=0.33\textwidth]{./pic/varorder1.eps}
  \includegraphics[width=0.66\textwidth]{./pic/varorder2.eps}
  \caption{ROBDD для
    \mbox{$(x_1 \Leftrightarrow x_2) \land (x_3 \Leftrightarrow x_4) \land (x_5 \Leftrightarrow x_6)$} и
    \mbox{$(x_1 \Leftrightarrow x_4) \land (x_2 \Leftrightarrow x_5) \land (x_3 \Leftrightarrow x_6)$}
  }\label{varorder}
\end{figure}

\newpage
\mbox{}
\newpage
\section*{English version}
\righthyphenmin=2
\sloppy
\thispagestyle{empty}
\bc
{\it Dmitry A. Ivanov, Andrey N. Terekhov}
\\
\Large {\bf Breadth-first search application for recursive problems}

\ec
\normalsize
\subsection*{Abstract}

\hspace*{0.6cm} The paper is devoted to application of breadth-first search technique for recursive problem solving. Formal definitions and algorithm templates for the new method are observed (decision graph is defined implicitly by recursive invocations). Binary decision diagram (BDD) is used as recursive context storage data structure. Upgraded BDD for arbitrary data storage is observed and framework of new technique is given. Algorithms are applied for well-known problems and performance results are compared with execution time of classic algorithms.


\end{document} 